home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_400 / 412_01 / src / bisear / bisearch.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  1994-03-29  |  5.8 KB  |  214 lines
  1. #include <new.h>
  2. #include "bisearch.h"
  3.  
  4. /*                      BISEARCH_
  5.  
  6.     The constructor puts the start node on s_open, the goal node on
  7.     t_open and sets the number of operators to the specified value.
  8.  
  9. */
  10.  
  11. BISEARCH_::BISEARCH_(NODE_ *start, NODE_ *goal, int num)
  12. {
  13.     s_open.addtohead(*start);   // add start node to the head of s_open
  14.     t_open.addtohead(*goal);    // add goal node to the head of t_open
  15.     num_op = num;
  16. }
  17.  
  18.  
  19.  
  20. /*                      ~BISEARCH_
  21.  
  22.     We don't make the destructor pure virtual because we can't be sure
  23.     a destructor will be defined in the derived class.
  24.  
  25. */
  26.  
  27. BISEARCH_::~BISEARCH_()
  28. {
  29. }
  30.  
  31.  
  32.  
  33. /*                      GENERATE
  34.  
  35.     Start looking for a solution and print it if found.
  36.  
  37. */
  38.  
  39. #ifdef MSC
  40.     extern int no_mem(size_t);
  41. #else
  42.     extern void no_mem();
  43. #endif
  44.  
  45. void BISEARCH_::generate()
  46. {
  47.     NODE_
  48.         *node,
  49.         *s_node,
  50.         *t_node;
  51.  
  52. #ifdef MSC
  53.     _set_new_handler(no_mem);
  54. #else
  55.     set_new_handler(no_mem);
  56. #endif
  57.  
  58.     if (!(node = bisolve()))
  59.     {
  60.         puts("No solution found");
  61.         return;
  62.     }
  63.  
  64. /* solve() stores the node that connects x_open with y_closed, i.e., the node
  65.    that is on both of these lists, at the head of x_open and of y_closed. */
  66.  
  67.     s_node = (NODE_ *) s_open.gethead();
  68.     t_node = (NODE_ *) t_open.gethead();
  69.  
  70. /* now find out on which list the node is stored: s_open or t_open. */
  71.  
  72.     if (node->equal(*s_node))
  73.     {
  74. /* first we print the first half of the path. Next we check if s_node
  75.    matches the tail node of t_closed, that is the goal node. If it does,
  76.    the search paths didn't connect and this means we already printed the
  77.    entire solution path. If it doesn't we still need to print the second
  78.    half of the solution path, starting with the parent of the first node
  79.    on y_closed. */
  80.  
  81.         print_sol(s_node);
  82.  
  83.         if (!s_node->equal(*t_closed.gettail()))
  84.             print_sol_2(((NODE_ *) t_closed.gethead())->getparent());
  85.               // as we searched backward we need a different printing routine
  86.     }
  87.     else   // apply the same procedure, but reversed
  88.     {
  89.         if (!t_node->equal(*s_closed.gettail()))
  90.             print_sol(((NODE_ *) s_closed.gethead())->getparent());
  91.  
  92.         print_sol_2(t_node);
  93.     }
  94. }
  95.  
  96.  
  97.  
  98. /*                      PRINT_SOL
  99.  
  100.     Trace back the solution path through the parent *'s. Recursively
  101.     prints that part of the solution path that reaches from the node
  102.     that connects both search paths back to the start.
  103.  
  104. */
  105.  
  106. void BISEARCH_::print_sol(NODE_ *sol) const
  107. {
  108.     if (!sol)
  109.         return;
  110.     print_sol(sol->getparent());
  111.     sol->display();
  112. }
  113.  
  114.  
  115.  
  116. /*                   PRINT_SOL_2
  117.  
  118.     Prints that part of the solution path that reaches from the node
  119.     connecting both search paths to the goal node.
  120.  
  121. */
  122.  
  123. void BISEARCH_::print_sol_2(NODE_ *sol) const
  124. {
  125.     while (sol)
  126.     {
  127.         sol->display();
  128.         sol = sol->getparent();
  129.     }
  130. }
  131.  
  132.  
  133.  
  134. /*                     BISOLVE
  135.  
  136.    This routine determines if the search will be continued backward or
  137.    forward. If s-open contains fewer nodes than t-open the search will
  138.    proceed forward, otherwise backward. If both lists are empty the
  139.    process ends with failure.
  140.  
  141. */
  142.  
  143. NODE_ *BISEARCH_::bisolve()
  144. {
  145.     NODE_
  146.         *node = NULL;
  147.  
  148.     while (node == NULL)
  149.     {
  150.         if(s_open.gethead() == NULL || t_open.gethead() == NULL)
  151.             break;    // no more nodes left in either list
  152.  
  153.         if (s_open.getcount() <= t_open.getcount())
  154.             node = solve(&s_open, &s_closed, &t_closed);  // search forward
  155.         else
  156.             node = solve(&t_open, &t_closed, &s_closed);  // search backward
  157.     }
  158.     return(node);
  159. }
  160.  
  161.  
  162.  
  163. /*                      SOLVE
  164.  
  165.     This routines implements the actual search engine. It takes the first
  166.     node from xOPEN, if xOPEN is empty the search process fails. If not,
  167.     the node is moved to xCLOSED. Next, the node's successors are generated
  168.     by calling NODE_::expand(). Then, every successor is made to point
  169.     back to its parent, so that the solution path may be traced back once
  170.     the solution is found. Next, the routine checks for every successor if
  171.     it is also on yClosed, i.e., if it is part of the other path of the
  172.     search process. If so, this means that the particular node connects
  173.     both paths and the search process halts. Each successor is passed to add()
  174.     for further processing, if add() returns 0 this means that the
  175.     successor already was on xOPEN and consequently it can be thrown away,
  176.     i.e. it gets deallocated.
  177.  
  178.     Solve() return the node that connects both paths if found and NULL
  179.     otherwise.
  180.  
  181. */
  182.  
  183. NODE_ *BISEARCH_::solve(SORTEDLIST_ *x_open, SORTEDLIST_ *x_closed, SORTEDLIST_ *y_closed)
  184. {
  185.     NODE_
  186.         *aux,
  187.         *father,
  188.         *child;
  189.  
  190.     father = (NODE_ *) x_open->gethead();   // get first node from open
  191.     x_open->remove_head();
  192.     x_closed->addtohead(*father);           // move it to closed
  193.  
  194.     child = father->expand(num_op);         // expand node
  195.     while (child)
  196.     {
  197.         child->setparent(father);           // sets up solution path
  198.  
  199.         if ((aux = (NODE_ *) y_closed->lookup(*child)) != NULL)
  200.         {                                 // here the paths connect
  201.             x_open->addtohead(*child);      // we store both of the nodes
  202.             y_closed->remove_found();       // at the start of the lists
  203.             y_closed->addtohead(*aux);  // so we can easily find them back
  204.             return(child);                // return node connecting both paths
  205.         }
  206.  
  207.         aux = child->getnext();
  208.         if (!add(x_open, x_closed, child))
  209.             delete(child);
  210.         child = aux;
  211.     }
  212.     return(NULL);
  213. }
  214.